Social networks are a key component of many systems ranging from instant messaging systems to media recommendation systems. One example of a social network based recommendation system is described in commonly owned and assigned U.S. patent application Ser. No. 11/484,130, entitled P2P NETWORK FOR PROVIDING REAL TIME MEDIA RECOMMENDATIONS, which was filed on Jul. 11, 2006 and is hereby incorporated herein by reference in its entirety. In general, social network based recommendation systems, such as that described in U.S. patent application Ser. No. 11/484,130, enable users to send media recommendations to and receive media recommendations from other users in a social network. However, one issue with social network based systems, including social network based recommendation systems, is the discovery of new friends. Traditionally, a user has been required to have prior knowledge of friends that the user desires to add to his or her social network or is allowed to select new friends from a global list of users. As such, there is a need for a system and method of quickly and easily discovering new friends for the user's social network.